package searchBack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NQueens {
    public static void main(String[] args) {
        solutionNQueens p = new solutionNQueens();
        // 皇后数
        int queens = 4;
        List<int[][]> res = p.solveNQueens(queens);
        System.out.println(res.toString());

    }

}


class solutionNQueens{
    // 用来存放没有问题的棋盘
    List<int[][]> res = new ArrayList<>();

    public List<int[][]> solveNQueens(int n){
        int[][] ven = new int[n][n];
        backTracks(ven, 0, 0);
        return res;
    }

    /**
     * 回溯函数
     * @param ven  棋盘
     * @param row  遍历到了第几行
     * @param n    放了几个皇后
     */
    public void backTracks(int[][] ven, int row, int n){
        System.out.println("我现在位于第"+row+"行");
        if(row == ven.length-1){

            for(int i=0;i<ven.length;i++)
                System.out.println(Arrays.toString(ven[i]));
            // 棋盘遍历结束
            if(n==ven.length){
                // 皇后添加完成
                int[][] tmp = new int[n][n];
                tmp = ven.clone();
                res.add(tmp);
            }
        }

        // 棋盘的列数
        int maxCol = ven[row].length;
        for(int col=0; col<maxCol; col++){
            // 判断该位置是否可以添加皇后
            if(!isValid(ven, row, col)){
                //System.out.println("row:"+ row +" col:"+col + "该位置无法放置");
                continue;
            }
            //System.out.println("row:"+ row +" col:"+col + "该位置可以放置");

            //添加皇后
            ven[row][col]=1;
            row = row+1;
            n = n+1;
            backTracks(ven, row, n);
            //回退操作
            ven[row][col]=0;
            row = row-1;
            n = n-1;
        }
    }


    /**
     * 判断该位置是否能够放皇后
     * @param ven 棋盘
     * @param row 位置的行
     * @param col 位置的列
     * @return 如果能够放就返回true， 不然返回false
     */
    public boolean isValid(int[][] ven, int row, int col){
        // 由于是每一行回溯遍历的所以不需要管左下与右下
        // 列数
        int maxCol = ven[row].length;

        // 行
        for(int i=0; i<row; i++){
            // 某行该列中存在一个皇后
            if(ven[i][col]==1){
                return false;
            }
        }

        // 列
        for(int i=0; i<maxCol; i++){
            // 该行某列中存皇后
            if(ven[row][i]==1){
                return false;
            }
        }

        // 左上
        for(int i=0; i<row; i++){
            // 左上的行
            int tmpRow = row-i;
            // 左上的列
            int tmpCol = col-i;
            if(tmpRow<0 || tmpCol<0){
                // 有任何一个小于0代表已经遍历玩了
                break;
            }
            if(ven[tmpRow][tmpCol]==1){
                return false;
            }
        }


        // 右上
        for(int i=0; i<row; i++){
            // 左上的行
            int tmpRow = row-i;
            // 左上的列
            int tmpCol = col+i;
            if(tmpRow<0 || tmpCol>maxCol-1){
                // 行遍历完，或者列超过最大列数
                break;
            }
            if(ven[tmpRow][tmpCol]==1){
                return false;
            }
        }
        return true;
    }

}


